
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class MATHS {
    public int romanToInt(String s) {
        int Ro[]=new int[1000];
        Ro['I']=1;Ro['V']=5;Ro['X']=10;Ro['L']=50;Ro['C']=100;
        Ro['D']=500;Ro['M']=1000;
        int len=s.length();
        int sum=0;int temp=Ro[s.charAt(0)];
        int change=0;
        for (int i=0;i<len-1;i++){
            char c=s.charAt(i);
            char c1=s.charAt(i+1);
            int a=Ro[c];int b=Ro[c1];
            if(a==b) {temp+=b;}
            else if(a<b) {sum-=temp;change=-1;temp=b;}
            else if(a>b) {sum+=temp;change=1;temp=b;}
        }
        if(change==0){ sum+=temp;return sum;}
        char c=s.charAt(len-2);
        char c1=s.charAt(len-1);
        int a=Ro[c];int b=Ro[c1];
        if(a!=b){
            sum+=temp;
        }else {
            if(change==1){
                sum+=temp;
            }else {
                sum-=temp;
            }
        }
        return sum;
    }

    public List<String> fizzBuzz(int n) {
        List<String> result=new ArrayList<>();
        for(int i=1;i<=n;i++){
            if(i%3==0&&i%5==0){
                result.add("FizzBuzz");
            }else if(i%3==0){
                result.add("Fizz");
            }else if(i%5==0){
                result.add("Buzz");
            }else {
                result.add(String.valueOf(i));
            }
        }
        return result;
    }

    public boolean isPowerOfThree(int n) {
        if(n<=0)return false;
        int maxPower = (int) Math.pow(3,(int)(Math.log(0x7fffffff)/Math.log(3)));
        if(maxPower%n==0)return true;
        return false;
    }
    public static int countPrimes(int n) {
        boolean data[]=new boolean[n];
        if(n==0||n==1||n==2)return 0;
        data[0]=true;
        data[1]=true;
        data[2]=false;
        for (int i=2;i<n;i++){
            if(!data[i]){
                for (int j=2;j*i<n;j++){
                    data[j*i]=true;
                }
            }
        }
        int count =0;
        for (int i=0;i<n;i++){
            if(!data[i]) count++;
        }
        return count;
    }
}
